from typing import List
from collections import deque

# backtrace 回溯算法？
# bfs
# dfs


class Solution:
    def connect(self, x: str, y: str):
        diff = 0
        for i in range(len(x)):
            if x[i] == y[i]:
                continue
            diff += 1

        return diff == 1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        queue = deque()
        visited = set()

        queue.append((startGene, 0))
        visited.add(startGene)

        while queue:
            node, steps = queue.popleft()
            # visit
            if node == endGene:
                return steps

            for i in bank:
                if i in visited:
                    continue
                if self.connect(node, i):
                    queue.append((i, steps + 1))
                    visited.add(i)

        return -1
